// 文件名：list_merge_sort.cpp
// 目的：演示 std::list 的就地排序（sort）与归并合并（merge）。
// 要点：
//   - list::sort()：链表内部排序，复杂度 O(n log n)，不分配额外数组；
//   - list::merge(other)：将两个“已排序”的链表按序合并到当前链表，other 变为空；
//   - merge 要求两个参与合并的链表均已按同一比较准则排序，否则结果未定义。
// 说明：
//   - 本示例先分别对 a、b 排序，然后 a.merge(b) 得到最终有序序列，并验证 b 为空。

#include <list>
#include <iostream>

void printList(const std::list<int>& lst, const char* label) {
    std::cout << label << ":";
    for (int v : lst) {
        std::cout << ' ' << v;
    }
    std::cout << '\n';
}

int main() {
    std::list<int> a{5, 1, 9, 3};
    std::list<int> b{8, 2, 7, 4};

    a.sort(); // 升序排序
    b.sort(); // 升序排序

    printList(a, "Sorted A");
    printList(b, "Sorted B");

    a.merge(b); // b 变为空，a 成为合并后的有序序列（稳定合并）
    printList(a, "Merged");

    if (b.empty()) {
        std::cout << "List B is now empty after merge\n";
    }
    return 0;
}